package com.gaogzhen.datastructure.symbolTable;

import java.util.Arrays;
import java.util.HashSet;
import java.util.NoSuchElementException;
import java.util.Set;

/**
 * @author Administrator
 * @version 1.0
 * @description
 * @date 2022-11-12 19:33
 */
public class BinarySearchST<K extends Comparable<K>, V> extends AbstractSortedST<K, V>{

    private K[] keys;
    private V[] vals;
    private int size;
    private int capacity;

    public BinarySearchST(int initCapacity) {
        if (initCapacity < 0) {
            throw new IllegalArgumentException("Illegal Capacity: "+
                    capacity);
        }
        this.capacity = initCapacity;
        keys = (K[]) new Comparable[capacity];
        vals = (V[]) new Object[capacity];
    }

    @Override
    public K min() {
        checkEmpty();
        return keys[0];
    }

    @Override
    public K max() {
        checkEmpty();
        return keys[size - 1];
    }

    private void checkEmpty() {
        if (size == 0) {
            throw new NoSuchElementException("元素不存在");
        }
    }

    @Override
    public K floor(K key) {
        int i = rank(key);
        if (i == 0 && keys[0].compareTo(key) != 0) {
            return null;
        }
        return keys[i];
    }

    @Override
    public K ceiling(K key) {
        int i = rank(key);
        if (i == size) {
            return null;
        }
        return keys[i];
    }

    @Override
    public int rank(K key) {
        int lo = 0, hi = size - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int cmp = key.compareTo(keys[mid]);
            if (cmp < 0) {
                hi = mid - 1;
            } else if (cmp > 0) {
                lo = mid + 1;
            } else {
                return mid;
            }
        }

        return lo;
    }

    @Override
    public K select(int k) {
        checkIndex(k - 1);
        return keys[k];
    }

    @Override
    public V delete(int index) {
        checkIndex(index);
        V oldVal = vals[index];
        for (int i = index; i < size; i++) {
            keys[i] = keys[i + 1];
            vals[i] = vals[i + 1];
        }
        size--;
        return oldVal;
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引越界");
        }
    }

    @Override
    public V deleteMin() {
        return delete(0);
    }

    @Override
    public V deleteMax() {
        return delete(size - 1);
    }

    @Override
    public V delete(K key) {
        int k = rank(key);
        V oldVal = null;
        if (k < size && keys[k].compareTo(key) == 0) {
            // 删除
            oldVal = delete(k);
        }
        return oldVal;
    }


    @Override
    public int size(K lo, K hi) {
        int l = rank(lo);
        int h = rank(hi);
        if (h < l) {
            throw new IllegalArgumentException("范围上限小于范围下限");
        }
        return contains(hi) ? h - l + 1: h - l;
    }



    @Override
    public void put(K key, V value) {
        int k = rank(key);
        if (k < size && keys[k].compareTo(key) == 0) {
            vals[k] = value;
            return;
        }
        if (size == capacity) {
            throw new StackOverflowError("数组溢出");
        }
        for (int i = size - 1; i >= k; i--) {
            keys[i + 1] = keys[i];
            vals[i + 1] = vals[i];
        }
        keys[k] = key;
        vals[k] = value;
        size++;
    }

    @Override
    public V get(K key) {
        int i = rank(key);
        if (i < size && keys[i].compareTo(key) == 0) {
            return vals[i];
        }
        return null;
    }



    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterable<K> keys(K lo, K hi) {
        Set<K> keySet = new HashSet<>();
        int  h = rank(hi);
        for (int i = rank(lo); i < h; i++) {
            keySet.add(keys[i]);
        }
        if (contains(hi)) {
            keySet.add(keys[h]);
        }
        return keySet;
    }

    @Override
    public Iterable<K> keys() {
        return new HashSet<>(Arrays.asList(keys));
    }

    @Override
    public String toString() {
        if (size == 0) {
            return "{}";
        }

        StringBuilder sb = new StringBuilder();
        sb.append('{');
        for (int i = 0; i < size; i++) {
            sb.append(keys[i]).append("=").append(vals[i]);
            if (i != size - 1) {
                sb.append(", ");
            }
        }
        sb.append("}");
        return sb.toString();
    }
}
